package com.fzkj.sort;

import java.util.Arrays;

/**
 * 希尔排序
 * @author yaya
 */
public class ShellSort {

    /**
     * 希尔排序是在插入排序上的一种改进排序方式。希尔排序也叫做缩减增量排序。
     * 它通过比较相距一定间隔的元素来进行，各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。
     *
     * 希尔排序和插入排序的区别在于有一个gap的概念，插入排序每次 -1，而希尔排序每次 -gap
     */
    public static void main(String[] args) {
        int[] s = {81,94,11,96,12,35,17,95,28,58,41,75,15};
        int[] p = {9,1,2,5,7,4,8,10,25,11,43,23,6,3,5};

        sort(p);
        System.out.println(Arrays.toString(p));
    }

    public static void sort(int[] arr) {
        int j;
        for (int gap = arr.length / 2; gap >  0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                int tmp = arr[i];
                for (j = i; j >= gap && tmp < arr[j - gap]; j -= gap) {
                    arr[j] = arr[j - gap];
                }
                arr[j] = tmp;
            }
        }
    }
}
